package cnki.kg.algorithm;

import org.junit.jupiter.api.Test;

public class AddTwoNumbers {


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    @Test
    public void Test() {

    }

    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {

        ListNode p1 = l1, p2 = l2;
        ListNode dummy = new ListNode(-1);//哨兵节点
        ListNode p = dummy;
        int carry = 0; //进位
        int newVal = 0;
        //l1,l2都是倒序，所以是直接从个位遍历
        while (p1 != null || p2 != null || carry > 0) {
            newVal = (p1 == null ? 0 : p1.val) + (p2 == null ? 0 : p2.val) + carry;//空位补0,carry 首次为0，有进位则传给下一次
            carry = newVal / 10;
            newVal %= 10;
            p.next = new ListNode(newVal);
            p1 = p1 == null ? null : p1.next;
            p2 = p2 == null ? null : p2.next;
            p = p.next;
        }
        return dummy.next;

    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        String l1Str = "";
        while (l1 != null) {
            l1Str += l1.val;
            l1 = l1.next;
        }
        String l2Str = "";
        while (l2 != null) {
            l2Str += l2.val;
            l2 = l2.next;
        }
        int l1int = Integer.parseInt(l1Str);
        int l2int = Integer.parseInt(l2Str);
        int sum = l1int + l2int;
        String sumStr = String.valueOf(sum);
        int count = sumStr.length() - 1;
        ListNode res = new ListNode(Integer.parseInt(String.valueOf(sumStr.charAt(count))));
        count--;

        while (count >= 0) {
            res = new ListNode(Integer.parseInt(String.valueOf(sumStr.charAt(count))), new ListNode());
            res = res.next;
        }
        return res;
    }

    @Test
    public void Test2() {
        int count = 10;
        ListNode head = new ListNode();
        //addHead(count,head);
        afterInsert(count, head);
    }

    public void addNode(int count, ListNode head) {
        if (count == 0) return;
        if (head == null) {
            head = new ListNode(count);
            count--;
            addNode(count, head);
        }
        ListNode newNode = new ListNode(count);
        count--;
        addNode(count, newNode);
        head.next = newNode;

    }

    public void beforeInsert(int i, ListNode node) {
        if (i == 0) return;
        ListNode newNode = new ListNode();//创建新的结点
        newNode.val = i;//设置数据域
        newNode.next = null;
        node.next = newNode;
        i--;
        beforeInsert(i, newNode);
    }

    //头插法创建单链表  栈形式先进后出
    public void afterInsert(int i, ListNode node) {
        if (i == 0) return;
        ListNode newNode = new ListNode();//创建新的结点
        newNode.val = i;//设置数据域
        newNode.next = node.next;
        node.next = newNode;
        i--;
        afterInsert(i, node);
    }
}
